首先,我们将所有源点与汇点筛出来,然后从每一个源点dfs求出它到各汇点的路径数,题目中保证源点与汇点数量相同,我们记为。
那么,我们可以得到一个的矩阵。
先考虑路径不相交的情况(似乎大家思路都是这样),题目求的是一个排列的逆序对数,记为。那么,题目等价于求:
其中,表示i号源点走到号汇点的路径数。
结合上文,不难很难想到行列式。然后,你会发现,矩阵的行列式就是答案。
然后,我们考虑路径相交的情况,发现答案不变。

显然,路径相交了
我们考虑交换位置

还是相交的。
这虽然不能解决我们的问题,但我们发现,经过交换后,汇点序列的逆序对数奇偶性变了,也就是矩阵行列式的其中一项变号。同时,路径数却没有变。所以,两种情况相互抵消了!!!
所以,路径相交并不会影响答案,直接算行列式即可。
本代码由@Krain大佬修改,可能神似请见谅。
同时,求矩阵行列式时消元必须在整数范围内运算,需要用到辗转相除的高斯消元,此处不再赘述。
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 600;
int n , m , x , y , p , cnt;
int Ind[ MAXN + 5 ] , Outd[ MAXN + 5 ];
int s[ MAXN + 5 ][ MAXN + 5 ];
int tmp[ MAXN + 5 ] , f[ MAXN + 5 ][ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];
vector< int > S , T;
int Mo( long long x ) {
return ( x % p + p ) % p;
}
int Gauss( ) {
int Sign = 1;
for( int i = 1 ; i <= cnt ; i ++ ) {
for( int j = i + 1 ; j <= cnt ; j ++ ) {
int A = f[ i ][ i ] , B = f[ j ][ i ];
while( B ) {
int t = A / B; A %= B; swap( A , B );
for( int k = i ; k <= n ; k ++ )
f[ i ][ k ] = Mo( 1ll * f[ i ][ k ] - 1ll * t * f[ j ][ k ] );
swap( f[ i ] , f[ j ] );
Sign *= -1;
}
}
if( !f[ i ][ i ] ) return 0;
}
int Ans = 1;
for( int i = 1 ; i <= cnt ; i ++ )
Ans = ( 1ll * Ans * f[ i ][ i ] ) % p;
return Mo( 1ll * Ans * Sign );
}
bool vis[ MAXN + 5 ];
void dfs( int u ) {
vis[ u ] = 1;
if( !Outd[ u ] ) s[ u ][ u ] = 1;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( !vis[ v ] ) dfs( v );
for( int j = 0 ; j < T.size() ; j ++ )
s[ u ][ T[ j ] ] = Mo( 1ll * s[ u ][ T[ j ] ] + s[ v ][ T[ j ] ] );
}
}
int main( ) {
scanf("%d %d %d",&n,&m,&p);
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d",&x,&y);
Graph[ x ].push_back( y );
Outd[ x ] ++ , Ind[ y ] ++;
}
for( int i = 1 ; i <= n ; i ++ ) {
if( !Ind[ i ] )
S.push_back( i );
if( !Outd[ i ] )
T.push_back( i );
}
for( int i = 1 ; i <= n ; i ++ )
if( !Ind[ i ] ) dfs( i );
for( int i = 0 ; i < S.size() ; i ++ )
for( int j = 0 ; j < T.size() ; j ++ )
f[ i + 1 ][ j + 1 ] = s[ S[ i ] ][ T[ j ] ];
cnt = S.size();
printf("%d",Gauss( ));
return 0;
}